package database

import (
	"JoRedis/util"
)

type Heap struct {
	dataSlc []interface{}
	size    int
	/** true:最小堆，false:最大堆 **/
	minFlag bool
}

/**
 * 创最大堆
 * 堆--数组形式实现(跨索引: i*2)
 * 将二叉树的节点按照层级顺序放入数组中,根节点在位置1(i),它的子节点在位置2(i*2)和3(i*2+1),而子节点的子节点则分别在位置4(i*2*2),5(i*2*2+1)和6,7,以此类推
 * 1.New()创建最大堆,NewMin()创建最小堆
 * 2.左子节点和右子节点的大小不区分
 * 3.插入新的节点时首先放入堆的最后,通过上浮来调整堆结构
 * 4.弹出最大节点(根节点)时,把堆最后元素交换到根节点上,通过下浮来调整堆结构(先比较左右子节点较大值,再把当前节点与较大值比较)
 * @author zhangyy
 */
func MakeHeap() *Heap {
	dataSlc := make([]interface{}, 20, 40)
	heapPtr := &Heap{
		dataSlc: dataSlc,
		size:    0,
		minFlag: false,
	}
	return heapPtr
}

// MakeMinHeap 创建最小堆
func MakeMinHeap() *Heap {
	dataSlc := make([]interface{}, 20, 40)
	heapPtr := &Heap{
		dataSlc: dataSlc,
		size:    0,
		minFlag: true,
	}
	return heapPtr
}

// Put 添加数据
func (this *Heap) Put(data interface{}) {
	this.dataSlc[this.size] = data
	this.moveUp(this.size)
	this.size++
}

// Pop 弹出第一个元素
func (this *Heap) Pop() interface{} {
	if this.size == 0 {
		return nil
	}
	data := this.dataSlc[0]
	// 第一个元素和最后一个元素互换
	this.dataSlc[0], this.dataSlc[this.size-1] = this.dataSlc[this.size-1], this.dataSlc[0]
	// 换后的最后元素置为nil
	this.dataSlc[this.size-1] = nil
	this.size--
	this.moveDown()
	return data
}

// Top 获取第一个元素
func (this *Heap) Top() interface{} {
	if this.size == 0 {
		return nil
	}
	return this.dataSlc[0]
}

// moveUp 上浮
func (this *Heap) moveUp(idx int) {
	for {
		if this.swap(idx, idx/2) {
			// 交换后继续上浮
			idx = idx / 2
		} else {
			break
		}
	}
}

// moveDown 下移
func (this *Heap) moveDown() {
	var idx = 0
	var swapIdx int
	for {
		if idx*2 < this.size && idx*2+1 < this.size {
			if idx*2+2 >= this.size {
				// 索引超出
				swapIdx = this.size - 1
			} else {
				if this.compare(idx*2+1, idx*2+2) {
					// 跟左子节点交换
					swapIdx = idx*2 + 1
				} else {
					// 跟右子节点交换
					swapIdx = idx*2 + 2
				}
			}
		} else {
			break
		}
		// 为了和moveUp函数复用swap函数，把swapIdx和idx的入参位置互换
		if this.swap(swapIdx, idx) {
			// 交换后继续下移
			idx = swapIdx
		} else {
			break
		}
	}
}

//  swap 交换值
//  true:交换--还需要继续交换，false:不交换--不需要继续交换（退出循环）
func (this *Heap) swap(childIdx int, parentIdx int) bool {
	if this.compare(childIdx, parentIdx) {
		// 交换
		this.dataSlc[childIdx], this.dataSlc[parentIdx] = this.dataSlc[parentIdx], this.dataSlc[childIdx]
		return true
	} else {
		return false
	}
}

// compare 比较,放在前面的为true
func (this *Heap) compare(childIdx int, parentIdx int) bool {
	if this.minFlag {
		// 最小堆
		return !util.Compare(this.dataSlc[childIdx], this.dataSlc[parentIdx])
	} else {
		// 最大堆
		return util.Compare(this.dataSlc[childIdx], this.dataSlc[parentIdx])
	}
}
